#include <iostream>
#include <vector>
#include <stack>

using namespace std;

class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};

class Solution {
public:
    void __preorder(Node *root, vector<int> &ans){
        if(root == NULL) return;
        ans.emplace_back(root->val);
        for(auto & x: root->children){
            __preorder(x, ans);
        }
        return;
    }
    vector<int> preorder(Node* root) {
        vector<int> ans;
        __preorder(root, ans);
        return ans;
    }
	
    // iteration method
    // vector<int> preorder(Node* root) {
    //     vector<int>res;
    //     if(!root) return res;
    //     stack<Node*>stk;
    //     stk.push(root);
    //     while(!stk.empty()){
    //         Node* tmp=stk.top();
    //         stk.pop();
    //         res.emplace_back(tmp->val);
    //         for(int i=tmp->children.size()-1; i>=0; --i){
    //             stk.push(tmp->children[i]);
    //         }
    //     }
    //     return res;
    // }
};

int main() {
    // 创建一个示例 N 叉树
    Node* root = new Node(1);
    root->children.push_back(new Node(3));
    root->children.push_back(new Node(2));
    root->children.push_back(new Node(4));
    root->children[0]->children.push_back(new Node(5));
    root->children[0]->children.push_back(new Node(6));

    // 进行前序遍历
    Solution sol;
    vector<int> result = sol.preorder(root);

    // 打印结果
    cout << "Preorder Traversal: ";
    for (int num : result) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}